This invention relates to coding and, more particularly, to trellis coding.
In recent years, successively refinable or rate-scalable source coders have received growing attention. By selecting different sub-streams of the output of such coders, various levels of encoding rate and distortion can be achieved.
One immediate application of rate-scalability is in progressive transmission. Sometimes the utility of progressive transmission is readily apparent because it is central to an application. One important example is in telemedicine, where a specialist must sort through and retrieve a large number of medical images over a network. If the images can be transmitted progressively so that unneeded images, or sections of images, can be identified before they have been transmitted with high fidelity, then cost and bandwidth can be saved. A similar application is the transmission of maps in which a low-resolution map of a big area can be transmitted first. The user can identify a specific area in the received map and request a high-resolution map of the specified region.
Another application of an embedded bit stream is in the transmission of video over an asynchronous transfer mode (ATM) network where some ATM cells may be lost in transit through the network. A video coder with an embedded output bit stream can mark the ATM cells with an importance measure; as a video frame is coded progressively, the descriptions become successively less important since they contribute less to the reduction of distortion. Cells in the network can then be dropped preferentially based upon their importance in distortion reduction.
Also, when multicasting over heterogeneous networks, rate-scalability provides the opportunity of using one bit stream for all receivers and intelligently dropping the less important portions of the bit stream for users with less available bandwidth.
Additionally, in many practical applications where the signal is transmitted over a noisy channel, the rates of the source and channel codes must be adjusted according to the level of noise in the channel. If the channel is a time-varying channel, as it is in many wireless communication situations, it is prudent to adaptively vary the rate allocation between the source and channel coding operations. Successive refinability allows the possibility of adapting the rate of the source encoder in a straightforward manner. Of course, similar rate-scalability features are needed for the channel coding part.
A powerfull source coding scheme for memoryless sources is trellis coded quantization (TCQ). See M. W. Marcellin and T. R. Fischer, "Trellis coded quantization of memoryless and Gauss-Markov sources," IEEE Trans. Comm., Vol. 38, January 1990, pp. 82-93. It has been shown that for a memoryless uniform source, trellis coded quantizers provide mean squared errors (MSEs) within 0.21 dB of the theoretical distortion bounds (for given rates). The performance of a TCQ is much better than that of the best scalar quantizer (Lloyd-Max quantizer) at the same rate.
Until now, it has been thought that trellis coding does not lend itself to successive refinability. In "Multi-state trellis coded quantization (MS-CW)", reported by H. A. Aksu and M. Salehi, in Proc. Conf. Inform. Sciences and Systems,Baltimore, Md., March 1995, the idea of multi-stage quantization is combined with that of TCQ. Therein, each stage of TCQ quantizes the error between the original and the quantized output of the previous stage. Unfortunately, multi-stage TCQ (MS-TCQ) suffers from about 2 dB performance degradation compared to the performance of TCQ. In "Progressive transmission in trellis coded quantization-based image coders," P. J. Sementilli et al, reported in Conf. Image Processing, Santa Barbara, Calif., October 1997, the TCQ structure is preserved and trellis coding is applied, but only to the last stage. Using a successive approximation-type setting, the inverse TCQ operation is performed only approximately for all intermediate stages. The resulting quantization scheme has been utilized for progressive transmission of images, but it doesn't take full advantage of the trellis structure.